AlphaGo背后的搜索算法：蒙特卡罗树搜索

深度学习 + 增强学习

启发式算法

蒙特卡洛树搜索

“蒙特卡洛树搜索”是一种启发式的搜索策略，能够基于对搜索空间的随机抽样来扩大搜索树，从而分析围棋这类游戏中每一步棋应该怎么走才能够创造最好机会。

一位名叫苏椰的知乎用户举了这样一个例子，以通俗的语言进行了解释：假如筐里有100个苹果，让我每次闭眼拿1个，挑出最大的。于是我随机拿1个，再随机拿1个跟它比，留下大的，再随机拿1个……我每拿一次，留下的苹果都至少不比上次的小。拿的次数越多，挑出的苹果就越大，但我除非拿100次，否则无法肯定挑出了最大的。这个挑苹果的算法，就属于蒙特卡罗算法：尽量找好的，但不保证是最好的。

需要说明的是，蒙特卡罗树搜索并不是只有一种算法，而是一类算法。其中最流行的算法之一就是UCT（upper confidence bounds applied to trees）。

占坑

alphago为什么不采用维特比算法？

因为alphago的路径搜索，跟markov不同。

markov有个状态转移矩阵，有限状态。围棋的状态空间太大，没办法用状态转移矩阵来衡量吧？

alpha-zero